package com.leetcode.根据情景进行分类;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2021/3/23
 * @description: 341. 扁平化嵌套列表迭代器
 * https://leetcode-cn.com/problems/flatten-nested-list-iterator/
 */
public class B_341_扁平化嵌套列表迭代器 {

	public static void main(String[] args) {

	}

	static void test1() {
		List<NestedInteger> nestedList = new ArrayList<>();
		nestedList.add(new MyNestedInteger());
		NestedIterator i = new NestedIterator(nestedList);
		while (i.hasNext()) {
			i.next();
		}
	}

	/**
	 * 嵌套的 list 也有可能为空集合的情况，即 list.size()==0
	 */
	static class NestedIterator implements Iterator<Integer> {

		/**
		 * index：nestedList 的索引；
		 */
		int index = 0, len = 0;

		List<NestedInteger> nestedList;
		/**
		 * 使用一个数组方便遍历
		 */
		NestedIterator[] iteratorArr;


		public NestedIterator(List<NestedInteger> nestedList) {
			if (nestedList == null){
				return;
			}
			this.len = nestedList.size();
			this.nestedList = nestedList;
			iteratorArr = new NestedIterator[len];
			for (int i = 0; i < len; i++) {
				if (nestedList.get(i).isInteger()) {
//					iteratorArr[i]=null;
				} else {
//					if (nestedList.get(i).getList().size() > 0) {
//						iteratorArr[i] = new NestedIterator(nestedList.get(i).getList());
//					}
					iteratorArr[i] = new NestedIterator(nestedList.get(i).getList());
				}
			}
		}

		/**
		 * 假设已经经过了 hasNext 的判断
		 * index 指的是当前
		 *
		 * @return
		 */
		@Override
		public Integer next() {
//			if (!hasNext()){
//				return null;
//			}
			NestedIterator iterator = iteratorArr[index];
			if (iterator == null) {
				return nestedList.get(index++).getInteger();
			}
			//此时 index 指的是一个 iterator
			Integer next = iterator.next();
			if (!iterator.hasNext()) {
				//如果 index 处的 iterator 已经达到了尽头，那么 index++
				index++;
			}
			return next;
		}

		/**
		 * index 指向当前元素，只是作为查看，而不移动指针
		 * 假设 index 已经被移动到正确的位置上了
		 *
		 * @return
		 */
		@Override
		public boolean hasNext() {
//			return (index != len) && (iteratorArr[index] == null || iteratorArr[index].hasNext());
			if (index == len) {
				return false;
			}
			if (iteratorArr[index] == null) {
				return true;
			}
			//如果 iteratorArr[index] != null 但是木有元素
			while (iteratorArr[index] != null && iteratorArr[index].isEmpty()) {
				//遇到空迭代，进位
				index++;
				if (index == len) {
					return false;
				}
			}
			//此时 index 指向 list
			return true;
		}

		/**
		 * 返回 容量是否为 0
		 * @return
		 */
		public boolean isEmpty() {
			return len == 0;
		}
	}

	interface NestedInteger {

		// @return true if this NestedInteger holds a single integer, rather than a nested list.
		public boolean isInteger();

		// @return the single integer that this NestedInteger holds, if it holds a single integer
// Return null if this NestedInteger holds a nested list
		public Integer getInteger();

		// @return the nested list that this NestedInteger holds, if it holds a nested list
// Return null if this NestedInteger holds a single integer
		public List<NestedInteger> getList();
	}

	static class MyNestedInteger implements NestedInteger {

		List<Integer> list = new ArrayList<Integer>();
		Integer i;

		public MyNestedInteger(Integer param) {
			i = param;
		}

		public MyNestedInteger(List<Integer> list) {
			this.list = list;
		}

		public MyNestedInteger() {
		}

		@Override
		public boolean isInteger() {
			return i != null;
		}

		@Override
		public Integer getInteger() {
			return i;
		}

		@Override
		public List<NestedInteger> getList() {
			return new ArrayList<>();
		}
	}
}
